#!/usr/bin/python
# N queens problem using blind search
# By Anderson Carvalho, Caio Almeida, Efraim Machado, Flavio Escobar and Paulo Henrique
# DCC/UFBA - MATA64 - 2009.2

# Our N
# Pass your desired value as a command line argument
# If none is passed, 4 will be used
import sys
n = 4
if len(sys.argv) > 1:
	n = int(sys.argv[1])

# Factorial
def factorial(x):
	if x == 0 or x == 1:
		return x
	else:
		return x*factorial(x-1)

# The number of tries is the number of times that we check for a goal state
tries = 0

# Maximum number of tries: arrangement (permutation), A(p,r), where p = n*n and r = n, so it's p!/(p-r)! 
maxtries = factorial(n*n)/factorial(n*n-n)

# Build an empty chess board of dimensions n x n
def build_board():
	board = []
	for i in range(n):
		row = []
		for j in range(n):
			row.append('-')
		board.append(row)
	return board
	
# Print the board
def print_board(board):
	for i in board:
		for j in i:
			print j,
		print

# Are there queens attacking each other?
# That's so ugly...
def none_attacked(board):
	for x in range(n):
		for y in range(n):
			if board[x][y] == '*':
				board[x][y] = '-'
				for i in range(n):
					for j in range(n):
						if ((board[i][j] == '*') and ((i - j == x - y) or (i + j == x + y) or (x == i) or (y == j))):
							board[x][y] = '*'
							return False
				board[x][y] = '*'
	return True

# Goal state: N queens on the board, none attacked
def goal_state(k, board):
	if k == n and none_attacked(board):
		return True
	return False

# Blind search for solutions
def blind_search(board, queens):
	# Increment number of tries
	global tries
	if queens == n:
		tries += 1

	# Iterate through all the chess board and put the queen on each empty position
	for x in range(n):
		for y in range(n):
			if board[x][y] == '-':
				board[x][y] = '*'

				# Check for goal state
				if goal_state(queens + 1, board):
					print 'Solution for', n, 'queens puzzle found after', tries, '/', maxtries, 'tries! See below:'
					print_board(board)
					exit(0)
				
				# Put remaining queens on the board
				if queens < n:
					blind_search(board, queens + 1)

				# Undo the positioning for next loop iteration
				board[x][y] = '-'

# Start with an empty board
blind_search(build_board(), 0)
print 'No solution found for', n, 'queens puzzle after', tries, '/', maxtries, 'tries.'
